package leetcode.code0882;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {

	public int reachableNodes(int[][] edges, int maxMoves, int n) {
		int cnts[][] = new int[n][n];
		List<Integer>[] nexts = new ArrayList[n];
		for (int i = 0; i < nexts.length; i++) {
			nexts[i] = new ArrayList<>();
		}
		for (int i = 0; i < edges.length; i++) {
			int[] e = edges[i];
			int u = e[0], v = e[1], cnt = e[2];
			cnts[u][v] = cnt;
			cnts[v][u] = cnt;
			nexts[u].add(v);
			nexts[v].add(u);
		}
		int[] start = new int[n];
		Arrays.fill(start, -1);
		start[0] = maxMoves;
		PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> start[b] - start[a]);// 出发点
		queue.add(0);
		int ans = 0;
		while (!queue.isEmpty()) {
//			int[] cur = queue.poll();
//			int u = cur[0], move = cur[1];
			int u = queue.poll(), move = start[u];
			ans++;
			List<Integer> next = nexts[u];
			for (int v : next) {
				if (start[v] == -1 && move - cnts[u][v] > 0) {
					queue.add(v);
				}
				start[v] = Math.max(start[v], move - cnts[u][v] - 1);
			}
		}
		for (int i = 0; i < edges.length; i++) {
			int[] e = edges[i];
			int u = e[0], v = e[1], cnt = e[2];
			ans += Math.min(cnt, Math.max(start[u], 0) + Math.max(start[v], 0));
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(40,
				this.reachableNodes(
						H.str2array1(
								"[[0,3,8],[0,1,4],[2,4,3],[1,2,0],[1,3,9],[0,4,7],[3,4,9],[1,4,4],[0,2,7],[2,3,1]]"),
						8, 5));
		H.compare(301, this.reachableNodes(H.str2array1(
				"[[1,3,23],[3,5,19],[3,6,17],[1,5,14],[6,7,20],[1,4,10],[1,6,0],[3,4,20],[1,7,4],[0,4,10],[0,7,9],[2,3,3],[3,7,9],[5,7,4],[4,5,16],[0,1,16],[2,6,0],[4,7,11],[2,5,14],[5,6,22],[4,6,12],[0,6,2],[0,2,1],[2,4,22],[2,7,20]]"),
				19, 8));

		H.compare(18, this.reachableNodes(H.str2array1("[[2,4,2],[3,4,5],[2,3,1],[0,2,1],[0,3,5]]"), 14, 5));
		H.compare(13, this.reachableNodes(H.str2array1("[[0,1,10],[0,2,1],[1,2,2]]"), 6, 3));
		H.compare(23, this.reachableNodes(H.str2array1("[[0,1,4],[1,2,6],[0,2,8],[1,3,1]]"), 10, 4));
		H.compare(1, this.reachableNodes(H.str2array1("[[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]]"), 17, 5));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		int[] arr = new int[] { 1, 3, 2 };
		PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> arr[b] - arr[a]);
		queue.add(0);
		queue.add(1);
		queue.add(2);
		while(!queue.isEmpty()) {
			System.out.println(queue.poll());
		}
	}

}
